布隆过滤器

布隆计算器——通过二进制向量的长度以及允许出错的值判断所需的哈希函数及向量的大小

1. 介绍

布隆过滤器（Bloom Filter）是1970年由布隆提出的。布隆过滤器实际上是一个很长的二进制向量和好几个哈希函数组成。

2. 原理

先贴个Java的简易实现。

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{3, 13, 46, 71, 91, 134};

    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            // 怎么来的...
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

基本原理：

首先要知道一个二进制数有0或1两种状态，而这两种状态可以表达两个值，比如性别：1男0女。

那么，一个二进制向量（用BitSet位数组表示），就是许多个二进制数组成的数组。在对一个元素进行哈希后，通过截取等操作可以得到一个下标，将这个值设置成1的话，就可以表示这个元素存在了。

但是，这远远不够，因为不同的元素可能都会引用同一个下标，只用一个值来表达的话，误判率会比较高。

一个不行就来多个，布隆过滤器通过多个种子构建成多个哈希函数，在添加一个元素的同时，会修改向量内多个下标的值，判断这个元素时候也会进行多次哈希，只有多次哈希出来的下标中的值都存在，则才能判断这个值可能存在，否则一定不存在。

3. 用途

可以用来校验某一个元素是否可能不存在于集合中（布隆校验不存在就一定是不存在，布隆校验存在则不一定存在）。

解决Redis缓存穿透问题。
邮件黑名单过滤。
爬虫过滤，判断是否重复。

4. 优点

耗时少。
性能高。
占用空间小。
保密性强，不存储元素本身。

5. 缺点

不能直接取到元素。
有误判几率。
删除困难，仅比较适合不进行删除和修改的场景。

6. 应用

真正使用的时候，可以使用Google的Guava的布隆过滤器的实现，较为权威。

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

// 创建布隆过滤器对象
// 最多存放1500个整数的过滤器，允许误差为0.01
BloomFilter<Integer> filter = BloomFilter.create(
    Funnels.integerFunnel(),
    1500,
    0.01);
// 判断指定元素是否可能存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

Guava缺陷：只能单机使用。

分布式场景下，使用Redis提供的布隆过滤器。

Bloom Filter